package k3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Knapsack {
	private int totalWeight;
	private ArrayList<Item> items;
	private Comparator<Item> compItem;
	private Comparator<BagState> compBag;
	private BagState bestSet;
	
	
	public Knapsack(){
		compItem=new Comparator<Item>(){
			public int compare(Item i1, Item i2){
				return (int) Math.ceil(10*i2.value/i2.weight - 10*i1.value/i1.weight);
			}
		};
		compBag=new Comparator<BagState>(){
			public int compare(BagState t1, BagState t2){
				return t1.bound - t2.bound;
			}
		};
	}
	
	public BagState best_first_branch_and_bound(ArrayList<Item> items, int totalWeight){
		int i;
		this.items=items;
		this.totalWeight=totalWeight;
		Collections.sort(items, compItem);
		PriorityQueue<BagState> pq = new PriorityQueue<BagState>(compBag);
		BagState q, w;
		w=new BagState(-1, 0, 0, 0, null, false);
		bestSet = new BagState(-1, 0, 0, 0, null, false);
		w.bound=bound(w);
		pq.enqueue(w);
		while(! pq.isEmpty()){
			w=pq.dequeue();
			if(w.weight>totalWeight)continue;
			if(w.bound<=bestSet.value)break;
			DynamicArray<BagState> child = new DynamicArray<BagState>();
			if(w.level<items.size()-1){
				q=new BagState(w.level+1, w.value+items.get(w.level+1).value, w.weight+items.get(w.level+1).weight, 0,w,true);
				q.bound=bound(q);
				child.add(q);
				q=new BagState(w.level+1, w.value, w.weight, 0,w,false);
				q.bound=bound(q);
				child.add(q);
			}
			for(i=0;i<child.length();i++){
				q=child.get(i);
				if(q.bound<=bestSet.value)continue;
				if(q.weight>totalWeight)continue;
				if(q.value>bestSet.value)bestSet=q;
				if(q.bound>bestSet.value)pq.enqueue(q);
			}
		}
		return bestSet;
	}
	
	public BagState depth_first_branch_and_bound(ArrayList<Item> items, int totalWeight){
		int i;
		this.items=items;
		this.totalWeight=totalWeight;
		Collections.sort(items, compItem);
//		for(Item s : objects){
//			System.out.println(s.value + " " + s.weight);
//		}
		Stack<BagState> stack = new Stack<BagState>();
		BagState u, v;
		v=new BagState(-1, 0, 0, 0, null, false);
		bestSet = new BagState(-1, 0, 0, 0, null, false);
		v.bound=bound(v);
		stack.push(v);
		while(! stack.isEmpty()){
			v=stack.pop();
			if(v.weight>totalWeight)continue;
			if(v.bound<=bestSet.value)continue;
			DynamicArray<BagState> children = new DynamicArray<BagState>();
			if(v.level<items.size()-1){
				u=new BagState(v.level+1, v.value, v.weight, 0,v,false);
				u.bound=bound(u);
				children.add(u);
				u=new BagState(v.level+1, v.value+items.get(v.level+1).value, v.weight+items.get(v.level+1).weight, 0,v,true);
				u.bound=bound(u);
				children.add(u);
			}
			for(i=0;i<children.length();i++){
				u=children.get(i);
				if(u.bound<=bestSet.value)continue;
				if(u.weight>totalWeight)continue;
				if(u.value>bestSet.value)bestSet=u;
				if(u.bound>bestSet.value)stack.push(u);
			}
		}
		return bestSet;
	}
	
	int bound(BagState state){
		int i, j;
		int bound;
		int totalSize=state.weight;
		int totalValue=state.value;
		for(i=state.level+1;i<items.size();i++){
			if(totalSize+items.get(i).weight>totalWeight)break;
			totalSize+=items.get(i).weight;
			totalValue+=items.get(i).value;
		}
		if(totalSize>totalWeight)bound=-1;
		else if(i==items.size())bound=totalValue;
		else{
			bound=totalValue+(totalWeight-totalSize)*items.get(i).value/items.get(i).weight;
		}
		if(totalValue>bestSet.value && totalSize<=totalWeight){
			bestSet=new BagState(i-1, totalValue, totalSize, totalValue,state, true);//null must be changed!
			for(j=state.level+1;j<i;j++){
				bestSet.objects.add(items.get(j));
			}
		}
		return bound;
	}
	
	public ArrayList<Item> findObjectsAdded(BagState state){
		int i;
		ArrayList<Item> items = new ArrayList<Item>();
		while(true){
			if(state==null)break;
			if(state.objects.isEmpty()==false){
				for(i=0;i<state.objects.size();i++)items.add(state.objects.get(i));
			}
			else if(state.wasAdded){
				items.add(this.items.get(state.level));
			}
			state=state.prvState;
		}
		for(i=0;i<items.size()/2;i++){//reverse
			items.set(i, items.get(items.size()-1-i));
		}
		return items;
	}
}

